#include "base.h"
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution
{
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        ListNode *final = nullptr, *final_head = nullptr;
        while (1)
        {
            auto minlist = lists[0];
            auto minlist_i = 0;
            for (int i = 0; i < lists.size(); i++)
            {
                if (lists[i])
                {
                    // leftcnt++;
                    if (!minlist)
                    {
                        minlist = lists[i];
                    }
                    if (lists[i]->val < minlist->val)
                    {
                        minlist = lists[i];
                        minlist_i = i;
                    }
                }
            }
            if (final)
            {
                final->next = minlist;
                final = final->next;
            }
            else
            {
                final_head = final = minlist;
            }
            if (!lists[minlist_i])
            {
                break;
            }
            lists[minlist_i] = lists[minlist_i]->next;
            // if (!lists[minlist_i])
            // {
            //     leftcnt--;
            // }
        }
        return final;
    }
};

ListNode *make_arr_node_list(int arr[], int n)
{
    ListNode *a, *b = nullptr;
    a = b = new ListNode(arr[0]);
    for (int i = 1; i < n; i++)
    {
        a->next = new ListNode(arr[i]);
        a = a->next;
    }
    return b;
}

int main()
{
    int arr1[] = {1, 2, 4};
    int arr2[] = {1, 3, 4};
    auto a = make_arr_node_list(arr1, 3);
    auto b = make_arr_node_list(arr2, 3);
    vector<ListNode *> v;
    v.push_back(a);
    v.push_back(b);
    Solution().mergeKLists(v);

    return 0;
}